Abstract: The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. These solvers are the foremost method for solving various discrete optimization problems. Choosing cutting planes effectively is a major research topic in the theory and practice of integer programming.

In this talk, I will discuss our recent generalization theory that provides provable guarantees for machine learning approaches to cutting plane selection. These guarantees are obtained via a structural analysis of branch-and-cut, in which we pin down conditions for different cutting planes to lead to identical executions of branch-and-cut. I will present such guarantees for two cutting plane families of great practical importance: Chvátal-Gomory cuts and Gomory mixed integer cuts. Finally, I will discuss guarantees for parameter tuning in a general model of tree search, which yields the first provable guarantees for simultaneously tuning the main aspects of branch-and-cut: node selection, branching, and cutting plane selection.

Joint work with Nina Balcan, Tuomas Sandholm, and Ellen Vitercik